package WeeklyContest;

import java.util.*;

/**
 * @author:gao
 * @date:2020/7/1
 * @time:14:30
 * @version:0.0.1
 * @description:none
 */

public class W195 {
    public static void main(String[] args) {

    }
}

//1496. 判断路径是否相交
//class Solution {
//    class Pos{
//        int x;
//        int y;
//
//        @Override
//        public boolean equals(Object o) {
//            if (this == o) return true;
//            if (o == null || getClass() != o.getClass()) return false;
//            Pos pos = (Pos) o;
//            return x == pos.x &&
//                    y == pos.y;
//        }
//
//        @Override
//        public int hashCode() {
//            return Objects.hash(x, y);
//        }
//    }
//    public boolean isPathCrossing(String path) {
//        int x=0;
//        int y=0;
//        Set<Pos> set = new HashSet<>();
//        Pos pz = new Pos();
//        pz.x =x;
//        pz.y=y;
//        set.add(pz);
//        for(int i=0;i<path.length();i++){
//            char c = path.charAt(i);
//            switch (c){
//                case 'N' :
//                    y++;
//                    break;
//                case 'S' :
//                    y--;
//                    break;
//                case 'E' :
//                    x++;
//                    break;
//                case 'W' :
//                    x--;
//                    break;
//            }
//            Pos p = new Pos();
//            p.x = x;
//            p.y = y;
//            if(set.contains(p)) return true;
//            set.add(p);
//        }
//        return false;
//    }
//
//}

//1497. 检查数组对是否可以被 k 整除
//class Solution {
//    public boolean canArrange(int[] arr, int k) {
//        Map<Integer,Integer> map = new HashMap<>();
//        for(int a : arr){
//            a%=k;
//            if(a<0) a+=k;//处理负数
//            int target = k-a;
//            if(target==k) target=0;//处理倍数
//            if(map.containsKey(target)){
//                int v = map.get(target);
//                if(v==1)map.remove(target);
//                else map.put(target,v-1);
//            }else{
//                map.put(a,map.getOrDefault(a,0)+1);
//            }
//        }
//        return map.isEmpty();
//    }
//}

    //我的five写法
//class Solution {
//    public int numSubseq(int[] nums, int target) {
//        Arrays.sort(nums);
//        int ans =0;
//        int indexMid = Arrays.binarySearch(nums,target/2+1);
//        if(indexMid<0) indexMid = - indexMid -1;//应该的插入点，共有有indexMid 个符合要求
//        else indexMid--;//找到了不符合要求的第一个，符合要求的最后一个就是上一个
//        ans +=indexMid;//只包含一个的时候
//        int min = nums[0];
//        int maxIndex = Arrays.binarySearch(nums,target-min+1); //加一找下一个元素
//        if(maxIndex<0) maxIndex = -maxIndex -1 -1;//可选择的最大元素下标
//        else maxIndex--;
//        int minIndex =0;
//        if(maxIndex>minIndex) {//所有种可能
//            ans += (Math.pow(2.0, maxIndex + 1) - 1 - maxIndex - 1);
//            minIndex++;
//            maxIndex--;
//        }
//        while (minIndex<maxIndex){
//            if(nums[minIndex]+nums[maxIndex]>target){
//                ans-=(Math.pow(2.0,maxIndex-minIndex-1));
//
//            }
//            else{
//                maxIndex--;
//                minIndex++;
//            }
//        }
//    }
//}

//题解双指针
//    public int numSubseq(int[] nums, int target) {
//        Arrays.sort(nums);
//        int n = nums.length;
//        int mod = 1000000007;
//        int[] tmp = new int[n];
//        tmp[0] = 1;
//        for (int i = 1; i < n; i++) {
//            tmp[i] = (tmp[i - 1] << 1) % mod;
//        }
//        int res = 0;
//        int l = 0;
//        int r = nums.length - 1;
//        while (l <= r) {
//            if (nums[l] + nums[r] > target) {
//                r--;
//            } else {
//                res = (res + tmp[r - l]) % mod;
//                l++;
//            }
//        }
//        return res;
//    }

